package cn.suchan.jianzhi.q34_char;

import java.util.ArrayList;

/**
 * 知识点：第一个只出现一次的字符
 * 题目描述
 * 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,
 * 并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
 *
 * @author suchan
 * @date 2019/05/31
 */
public class Solution {

    private static final int MAX_LENGTH = 10000;

    /**
     * 一个个字符进行对比，如果已经出现过就用‘#’代替，循环对比的时候要忽略掉‘#’，
     * 在list中存储不重复字符的下标，返回list第一个值就是第一次出现的不重复字符下标了
     * ps：我的这个方法比下面那个方法更有效率
     *
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar(String str) {
        if (str == null || str.isEmpty() || str.length() > MAX_LENGTH) {
            return -1;
        }
        char[] chars = str.toCharArray();

        ArrayList<Integer> indexList = new ArrayList<>();
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] != '#') {
                int count = 1;
                for (int j = i + 1; j < chars.length; j++) {
                    if (chars[j] != '#' && chars[i] == chars[j]) {
                        // 把已经确认过相等的字符替换成‘#’，
                        // 这样就可以避免循环到这个字符的最后一个位置（i）的时候会把这个字符的位置存储起来
                        chars[j] = '#';
                        count++;
                    }
                }
                if (count == 1) {
                    indexList.add(i);
                }
            }
        }
        return indexList.get(0);
    }

    /**
     * 借鉴别人的做法
     *
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar1(String str) {
        if (str == null || str.isEmpty() || str.length() > MAX_LENGTH) {
            return -1;
        }
        // 存储不重复的字符
        ArrayList<Character> unique = new ArrayList<>();
        // 存储重复字符
        ArrayList<Character> repeated = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            Character c = str.charAt(i);
            if (!unique.contains(c) && !repeated.contains(c)) {
                unique.add(c);
            } else {
                // 如果unique或repeated中已经存在，则表明是已经出现过的字符
                // 这里无论是unique中存在还是repeated中存在，直接在unique中移除，并在respected中追加当前字符
                unique.remove(c);
                repeated.add(c);
            }
        }
        return str.indexOf(unique.get(0));
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.FirstNotRepeatingChar1("aabcddellssibercc"));
    }
}
